package com.smh;

import org.junit.jupiter.api.Test;

import javax.swing.tree.TreeNode;
import java.util.ArrayDeque;
import java.util.Stack;

/**
 * @author shiminghui
 * @date 2025/2/20 16:35
 * @description: TODO
 */
public class _031_二叉树_深度优先遍历 {

    @Test
    public void test1() {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);
     /*   depthFirstTraversal(root);
        System.out.println("------------");
        depthFirstTraversal2(root);
        System.out.println("------------");
        depthFirstTraversal3(root);
        System.out.println("------------");*/
        /*depthFirstTraversal4(root);
        System.out.println("------------");
        depthFirstTraversal5(root);
        System.out.println("------------");
        depthFirstTraversal6(root);*/
        System.out.println("------------");
        depthFirstTraversal7(root, 1);
    }

    // 深度优先遍历(前序)
    public void depthFirstTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.println(root.val);
        depthFirstTraversal(root.left);
        depthFirstTraversal(root.right);
    }

    // 深度优先遍历(中序)
    public void depthFirstTraversal2(TreeNode root) {
        if (root == null) {
            return;
        }
        depthFirstTraversal2(root.left);
        System.out.println(root.val);
        depthFirstTraversal2(root.right);
    }

    // 深度优先遍历(后序)
    public void depthFirstTraversal3(TreeNode root) {
        if (root == null) {
            return;
        }
        depthFirstTraversal3(root.left);
        depthFirstTraversal3(root.right);
        System.out.println(root.val);
    }

    // 深度优先遍历(前序)——栈实现
    public void depthFirstTraversal4(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.add(root);
        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            if (pop.right != null) {
                stack.add(pop.right);
            }
            if (pop.left != null) {
                stack.add(pop.left);
            }
            System.out.println(pop.val);
        }
    }

    // 深度优先遍历(中序)——栈实现
    public void depthFirstTraversal5(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (!stack.isEmpty() || cur != null) {
            if (cur != null) {
                stack.add(cur);
//                System.out.println(cur.val);
                cur = cur.left;
            } else {
                cur = stack.pop();
                System.out.println(cur.val);
                cur = cur.right;
            }
        }
    }

    // 深度优先遍历(后序)——栈实现
    public void depthFirstTraversal6(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode flag = null;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.add(cur);
                cur = cur.left;
            } else {
                TreeNode peek = stack.peek();
                if (peek.right == null || peek.right == flag) {  // 右子树为空或者右子树已经访问过了
                    flag = stack.pop(); // 记录上一个弹出的节点
                    System.out.println(flag.val);
                } else {
                    cur = peek.right;
                }
            }
        }
    }

    // 深度优先遍历（通用） -栈实现
    public void depthFirstTraversal7(TreeNode root, int order) {
        if (root == null) {
            return;
        }
        ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        TreeNode cur = root;
        TreeNode flag = null;
        while (cur != null || !deque.isEmpty()) {
            if (cur != null) {
                // 处理左子树之前
                deque.addLast(cur); // 节点入栈
                if (order == -1) {
                    System.out.println(cur.val); // 先序遍历
                }
                cur = cur.left;
            } else {
                TreeNode peek = deque.getLast();
                // 没有右子树
                if (peek.right == null) {
                    flag = deque.pollLast();
                    if (order == 0 || order == 1) {
                        System.out.println(peek.val); // 中序遍历 , 后序遍历
                    }
                }
                // 已处理右子树
                else if (peek.right == flag) {
                    flag = deque.pollLast();
                    if (order == 1) {
                        System.out.println(peek.val); // 后序遍历
                    }
                }
                // 处理右子树之前
                else {
                    if (order == 0) {
                        System.out.println(peek.val); // 中序遍历
                    }
                    cur = peek.right;
                }
            }
        }
    }

    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }

        TreeNode() {

        }

        TreeNode(TreeNode left, int x, TreeNode right) {
            this.left = left;
            val = x;
            this.right = right;
        }
    }

}
